{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 用列表定义一个栈"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "    def push(self,item):\n",
    "        self.items.append(item)\n",
    "    def pop(self):\n",
    "        return self.items.pop()\n",
    "    def peek(self):\n",
    "        return self.items[len(self.items)-1]\n",
    "    def isEmpty(self):\n",
    "        return self.items==[]\n",
    "    def size(self):\n",
    "        return len(self.items)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 简单括号匹配"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pythonds.basic.stack import Stack\n",
    "\n",
    "def parChecker(symbolString):\n",
    "    s = Stack()\n",
    "    balanced = True\n",
    "    index = 0\n",
    "    while index < len(symbolString) and balanced:\n",
    "        symbol = symbolString[index]\n",
    "        if symbol == \"(\":\n",
    "            s.push(symbol)\n",
    "        else:\n",
    "            if s.isEmpty():\n",
    "                balanced = False\n",
    "            else:\n",
    "                s.pop()\n",
    "        index = index + 1\n",
    "    if balanced and s.isEmpty():\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "# 创建实例要加括号"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "#大中小括号一起，通用的\n",
    "from pythonds.basic.stack import Stack\n",
    "\n",
    "def parChecker(symbolString):\n",
    "    s = Stack()\n",
    "    balanced = True\n",
    "    index = 0\n",
    "    while index < len(symbolString) and balanced:\n",
    "        symbol = symbolString[index]\n",
    "        if symbol in \"([{\":\n",
    "            s.push(symbol)\n",
    "        else:\n",
    "            if s.isEmpty():\n",
    "                balanced = False\n",
    "            else:\n",
    "                top = s.pop()\n",
    "                if not matches(top,symbol):\n",
    "                    balanced = False\n",
    "        index = index + 1\n",
    "    if balanced and s.isEmpty():\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "def matches(open,close):\n",
    "    opens = \"([{\"\n",
    "    closers = \")]}\"\n",
    "    return opens.index(open) == closers.index(close)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 十进制转换为二进制"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pythonds.basic.stack import Stack\n",
    " \n",
    "def divideBy2(decNumber):\n",
    "    remstack = Stack()\n",
    "    \n",
    "    while decNumber > 0:\n",
    "        rem = decNumber % 2\n",
    "        remstack.push(rem)\n",
    "        decNumber = decNumber //2\n",
    "        \n",
    "    binString = \"\"\n",
    "    while not remstack.isEmpty():\n",
    "        binString = binString + str(remstack.pop())\n",
    "    return binString"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#任意十六进制一下的进制\n",
    "from pythonds.basic.stack import Stack\n",
    " \n",
    "def baseConverter(decNumber,base):\n",
    "    digits = \"0123456789ABCDE\"\n",
    "    remstack = Stack()\n",
    "    \n",
    "    while decNumber > 0:\n",
    "        rem = decNumber % base\n",
    "        remstack.push(rem)\n",
    "        decNumber = decNumber //base\n",
    "        \n",
    "    newString = \"\"\n",
    "    while not remstack.isEmpty():\n",
    "        newString = newString + digits[remstack.pop()]\n",
    "    return newString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 表达式转换"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 中缀表达为后缀\n",
    "from pythonds.basic.stack import Stack\n",
    "\n",
    "def infixTopostfix(infixexpr):        \n",
    "    prec = {}\n",
    "    prec['*'] = 3                    #记录操作符优先级\n",
    "    prec['/'] = 3\n",
    "    prec['+'] = 2\n",
    "    prec['-'] = 2\n",
    "    prec['('] = 1\n",
    "    opStack = Stack()\n",
    "    postfixList = []\n",
    "    tokenList = infixexpr.split()     #解析表达式到单词列表\n",
    "    for token in tokenList:\n",
    "        if token in \"ABCDEFGHIJKLMNOPQRSTUVWXYZ\" or token in \"1234567890\":\n",
    "            postfixList.append(token)\n",
    "        elif token == '(':\n",
    "            opStack.push(token)\n",
    "        elif token == ')':\n",
    "            topToken = opStack.pop()\n",
    "            while topToken != '(':\n",
    "                postfixList.append(topToken)\n",
    "                topToken = opStack.pop()\n",
    "        else:\n",
    "            while (not opStack.isEmpty()) and \\\n",
    "            (prec[opStack.peek()] >= prec[token]):\n",
    "                postfixList.append(opStack.pop())\n",
    "            opStack.push(token)\n",
    "    while not opStack.isEmpty():\n",
    "        postfixList.append(opStack.pop())\n",
    "    return \"\".join(postfixList)\n",
    "\n",
    "#调用实例的函数加括号"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "#计算后缀表达式的值\n",
    "def postfixEval(postfixExpr):\n",
    "    operandStack = Stack()\n",
    "    tokenList = postfixExpr.split()\n",
    "    for token in tokenList:\n",
    "        if token in '0123456789':\n",
    "            operandStack.push(int(token))\n",
    "        else:\n",
    "            operand2 = operandStack.pop()\n",
    "            operand1 = operandStack.pop()\n",
    "            result = doMath(token,operand1,operand2)\n",
    "            operandStack.push(result)\n",
    "    return operandStack.pop()\n",
    "\n",
    "def doMath(op,op1,op2):\n",
    "    if op == '*':\n",
    "        return op1 * op2\n",
    "    elif op == '/':\n",
    "        return op1 / op2\n",
    "    elif op == '+':\n",
    "        return op1 + op2\n",
    "    else:\n",
    "        return op1 - op2\n",
    "\n",
    "#字符串的split要有空格才能分开"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 队列抽象数据类型"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "    \n",
    "    def enqueue(self,item):\n",
    "        self.items.insert(0,item)\n",
    "    def dequeue(self):\n",
    "        return self.items.pop()\n",
    "    def size(self):\n",
    "        return len(self.items)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False [True, 7]\n",
      "1 [True]\n"
     ]
    }
   ],
   "source": [
    "q = Queue()\n",
    "q.enqueue(7)\n",
    "q.enqueue(True)\n",
    "print(q.isEmpty(),q.items)\n",
    "q.dequeue()\n",
    "print(q.size(),q.items)\n",
    "\n",
    "#实例属性调用不能加括号"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 热土豆问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pythonds.basic.queue import Queue\n",
    "\n",
    "def hotPotato(namelist,num):\n",
    "    simqueue = Queue()\n",
    "    for name in namelist:\n",
    "        simqueue.enqueue(name)\n",
    "    \n",
    "    while simqueue.size() > 1:\n",
    "        for i in range(num):\n",
    "            simqueue.enqueue(simqueue.dequeue())\n",
    "        simqueue.dequeue()\n",
    "    return simqueue.dequeue()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Susan\n"
     ]
    }
   ],
   "source": [
    "print(hotPotato(['Bill','David','Susan','Jane','Kent','Brad'],7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 打印任务"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pythonds.basic.queue import Queue\n",
    "import random\n",
    "\n",
    "class Printer:\n",
    "    def __init__(self,ppm):\n",
    "        self.pagerate = ppm                           #打印速度\n",
    "        self.currentTask = None                      #打印任务\n",
    "        self.timeRemaining = 0                        #任务倒计时\n",
    "    \n",
    "    def tick(self):                                  #打印一秒\n",
    "        if self.currentTask != None:\n",
    "            self.timeRemaining = self.timeRemaining - 1\n",
    "            if self.timeRemaining <= 0:\n",
    "                self.currentTask = None\n",
    "    \n",
    "    def busy(self):                                  #打印机忙？\n",
    "        if self.currentTask != None:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    def startNext(self,newtask):                     #打印新作业\n",
    "        self.currentTask = newtask\n",
    "        self.timeRemaining = newtask.getPages() \\\n",
    "                             *60/self.pagerate\n",
    "\n",
    "class Task:\n",
    "    def __init__(self,time):\n",
    "        self.timestamp = time                      #生成时间戳\n",
    "        self.pages = random.randrange(1,21)        #打印页数\n",
    "    \n",
    "    def getStamp(self):\n",
    "        return self.timestamp\n",
    "    \n",
    "    def getPages(self):\n",
    "        return self.pages\n",
    "    \n",
    "    def waitTime(self,currenttime):                #等待时间\n",
    "        return currenttime - self.timestamp\n",
    "    \n",
    "def newPrintTask():\n",
    "    num = random.randrange(1,181)               #1/180概率生成作业\n",
    "    if num == 180:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "def simulation(numSeconds,pagesPerMinute):  #开始模拟\n",
    "    labprinter = Printer(pagesPerMinute)\n",
    "    printQueue = Queue()\n",
    "    waitingtimes = []\n",
    "    \n",
    "    for currentSecond in range(numSeconds):\n",
    "        \n",
    "        if newPrintTask():\n",
    "            task = Task(currentSecond)\n",
    "            printQueue.enqueue(task)\n",
    "        \n",
    "        if (not labprinter.busy()) and \\\n",
    "                    (not printQueue.isEmpty()):\n",
    "            nexttask = printQueue.dequeue()\n",
    "            waitingtimes.append(\\\n",
    "                    nexttask.waitTime(currentSecond))\n",
    "            labprinter.startNext(nexttask)\n",
    "            \n",
    "        labprinter.tick()\n",
    "    \n",
    "    averageWait = sum(waitingtimes)/len(waitingtimes)\n",
    "    print(\"Average Wait %6.2f secs %3d tasks remaining.\"\\\n",
    "           %(averageWait,printQueue.size()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 双端队列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Deque:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "    \n",
    "    def addFront(self,item):\n",
    "        self.items.append(item)\n",
    "    \n",
    "    def addReal(self,item):\n",
    "        self.items.insert(0,item)\n",
    "    \n",
    "    def removeFront(self):\n",
    "        return self.items.pop()\n",
    "    \n",
    "    def removeReal(self):\n",
    "        return self.items.pop(0)\n",
    "    \n",
    "    def size(self):\n",
    "        return len(self.items)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#回文词判定\n",
    "from pythonds.basic.deque import Deque\n",
    "\n",
    "def palchecker(aString):\n",
    "    chardeque = Deque()\n",
    "    \n",
    "    for ch in aString:\n",
    "        chardeque.addRear(ch)\n",
    "        \n",
    "    stillEqual = True\n",
    "    \n",
    "    while chardeque.size() > 1 and stillEqual:\n",
    "        first = chardeque.removeFront()\n",
    "        last = chardeque.removeRear()\n",
    "        if first != last:\n",
    "            stillEqual = False\n",
    "    \n",
    "    return stillEqual\n",
    "\n",
    "#print(palchecker('LSDKJFSKF'))\n",
    "#print(palchecker('radar'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 链表实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "93\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self,initdata):\n",
    "        self.data = initdata\n",
    "        self.next = None\n",
    "    \n",
    "    def getData(self):\n",
    "        return self.data\n",
    "    \n",
    "    def getNext(self):\n",
    "        return self.next\n",
    "    \n",
    "    def setData(self,newdata):\n",
    "        self.data = newdata\n",
    "    \n",
    "    def setNext(self,newnext):\n",
    "        self.next = newnext\n",
    "\n",
    "temp = Node(93)\n",
    "print(temp.getData())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "class UnorderedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "    \n",
    "    def add(self,item):\n",
    "        temp = Node(item)\n",
    "        temp.setNext(self.head)\n",
    "        self.head = temp\n",
    "    \n",
    "    def size(self):\n",
    "        current = self.head\n",
    "        count = 0\n",
    "        while current != None:\n",
    "            count = count + 1\n",
    "            current = current.getNext()\n",
    "        return count\n",
    "    \n",
    "    def search(self,item):\n",
    "        current = self.head\n",
    "        found = False\n",
    "        while current != None and not found:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                current = current.getNext()\n",
    "        return found\n",
    "     \n",
    "    def remove(self,item):\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        found = False\n",
    "        while not found:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.getNext()\n",
    "        \n",
    "        if previous == None:\n",
    "            self.head = current.getNext()\n",
    "        else:\n",
    "            previous.setNext(current.getNext())\n",
    "    \n",
    "    def append(self,item):\n",
    "        pass\n",
    "    \n",
    "    def pop(self):\n",
    "        pass\n",
    "\n",
    "mylist = UnorderedList()\n",
    "print(mylist.head)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 有序表OrderList"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Node定义相同\n",
    "class OrderedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "    \n",
    "    def search(self,item):\n",
    "        current = self.head\n",
    "        found = False\n",
    "        stop = False\n",
    "        while current != None and not found and not stop:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                if current.getData() > item:                #利用有序特征节省搜索时间\n",
    "                    stop = True\n",
    "                else:\n",
    "                     current = current.getNext()\n",
    "        return found\n",
    "    \n",
    "    def add(self,item):\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        stop = False\n",
    "        while current != None and not stop:\n",
    "            if current.getData() > item:\n",
    "                stop = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.getNext()\n",
    "            \n",
    "        temp = Node(item)\n",
    "        if previous == None:\n",
    "            temp.setNext(self.head)\n",
    "            self.head = temp\n",
    "        else:\n",
    "            temp.setNext(current)\n",
    "            previous.setNext(temp)\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 递归"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n"
     ]
    }
   ],
   "source": [
    "# 不用循环实现数列加法\n",
    "def listsum(numList):\n",
    "    if len(numList) == 1:\n",
    "        return numList[0]\n",
    "    else:\n",
    "        return numList[0] + listsum(numList[1:])\n",
    "print(listsum([1,2,3,4,5]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5AD\n"
     ]
    }
   ],
   "source": [
    "#任意进制转换\n",
    "def toStr(n,base):\n",
    "    convertString = '0123456789ABCDEF'\n",
    "    if n < base:\n",
    "        return convertString[n]\n",
    "    else:\n",
    "        return toStr(n//base,base) + convertString[n%base]\n",
    "print(toStr(1453,16))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "#螺旋线\n",
    "import turtle\n",
    "\n",
    "t = turtle.Turtle()\n",
    "\n",
    "def drawSpiral(t,lineLen):\n",
    "    if lineLen > 0:\n",
    "        t.forward(lineLen)\n",
    "        t.right(90)\n",
    "        drawSpiral(t,lineLen - 5)\n",
    "drawSpiral(t,200)\n",
    "turtle.done()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#分形树\n",
    "import turtle\n",
    "\n",
    "def tree(branch_len):\n",
    "    if branch_len > 5:\n",
    "        t.forward(branch_len)\n",
    "        t.right(20)\n",
    "        tree(branch_len - 15)\n",
    "        t.left(40)\n",
    "        tree(branch_len - 15)\n",
    "        t.right(20)\n",
    "        t.backward(branch_len)\n",
    "\n",
    "t = turtle.Turtle()\n",
    "t.left(90)\n",
    "t.penup()\n",
    "t.backward(200)\n",
    "t.pendown()\n",
    "t.pencolor('green')\n",
    "t.pensize(2)\n",
    "tree(105)\n",
    "t.hideturtle()\n",
    "turtle.done()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#谢尔宾斯基三角形\n",
    "import turtle\n",
    "\n",
    "def sierpinski(degree,points):\n",
    "    colormap = ['blue' , 'red' , 'green' , 'white' , 'yellow' , 'orange','pink']\n",
    "    drawTriangle(points,colormap[degree])             #points是一个字典\n",
    "    if degree > 0 :                   #调用自身，左上右次序\n",
    "        sierpinski(degree-1,\n",
    "                   {'left':points['left'],\n",
    "                    'top':getMid(points['left'],points['top']),\n",
    "                    'right':getMid(points['left'],points['right'])})\n",
    "        sierpinski(degree - 1,\n",
    "                  {'left':getMid(points['left'],points['top']),\n",
    "                   'top':points['top'],\n",
    "                   'right':getMid(points['top'],points['right'])})\n",
    "        sierpinski(degree - 1,\n",
    "                   {'left':getMid(points['left'],points['right']),\n",
    "                    'top':getMid(points['top'],points['right']),\n",
    "                    'right':points['right']})\n",
    "\n",
    "def drawTriangle(points,color):\n",
    "    t.fillcolor(color)\n",
    "    t.penup()\n",
    "    t.goto(points['top'])\n",
    "    t.pendown()\n",
    "    t.begin_fill()\n",
    "    t.goto(points['left'])\n",
    "    t.goto(points['right'])\n",
    "    t.goto(points['top'])\n",
    "    t.end_fill()\n",
    "    \n",
    "def getMid(p1,p2):\n",
    "    return ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)\n",
    "\n",
    "t = turtle.Turtle()\n",
    "\n",
    "points = {'left':(-200,-100),\n",
    "          'top':(0,200),\n",
    "          'right':(200,-100)}\n",
    "\n",
    "sierpinski(6,points)\n",
    "\n",
    "turtle.done()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Moving dist[1] from #1 to #3\n",
      "Moving dist[2] from #1 to #2\n",
      "Moving dist[1] from #3 to #2\n",
      "Moving dist[3] from #1 to #3\n",
      "Moving dist[1] from #2 to #1\n",
      "Moving dist[2] from #2 to #3\n",
      "Moving dist[1] from #1 to #3\n"
     ]
    }
   ],
   "source": [
    "#汉诺塔\n",
    "def moveTower(height,fromPole,withPole,toPole):\n",
    "    if height >= 1:\n",
    "        moveTower(height-1,fromPole,toPole,withPole)\n",
    "        moveDist(height,fromPole,toPole)\n",
    "        moveTower(height-1,withPole,fromPole,toPole)\n",
    "\n",
    "def moveDist(dist,fromPole,toPole):\n",
    "    print(f\"Moving dist[{dist}] from {fromPole} to {toPole}\")\n",
    "\n",
    "moveTower(3,'#1','#2','#3')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "-31.258016109466553\n"
     ]
    }
   ],
   "source": [
    "#硬币找零的递归解法\n",
    "import time\n",
    "def recMC(coinValueList,change):\n",
    "    minCoins = change\n",
    "    if change in coinValueList:\n",
    "        return 1\n",
    "    else:\n",
    "        for i in [c for c in coinValueList if c <= change]:     #对种币值都要求一次对应的最小的\n",
    "            numCoins = 1 + recMC(coinValueList,change-i)\n",
    "            if numCoins < minCoins:\n",
    "                minCoins = numCoins\n",
    "    return minCoins\n",
    "\n",
    "start = time.time()\n",
    "print(recMC([1,5,10,25],63))     #重复的计算太多了！！！！\n",
    "end = time.time()\n",
    "print(end - start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "#改进递归算法\n",
    "def recDC(coinValueList, change, knownResults):\n",
    "    minCoins = change\n",
    "    if change in coinValueList:            #最小结束条件\n",
    "        knownResults[change] = 1\n",
    "        return 1\n",
    "    elif knownResults[change] > 0:\n",
    "        return knownResults[change]     #查表成功，使用最优解\n",
    "    else:\n",
    "        for i in [c for c in coinValueList if c <= change]:\n",
    "            numCoins = 1 + recDC(coinValueList,change - i,knownResults)\n",
    "            if numCoins < minCoins:\n",
    "                minCoins = numCoins\n",
    "                #找到最优解，记录到表中\n",
    "                knownResults[change] = minCoins\n",
    "    return minCoins\n",
    "\n",
    "print(recDC([1,5,10,25], 63, [0]*64))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "#动态规划\n",
    "def dpMakeChange(coinValueList,change,minCoins):\n",
    "    #从1分钱开始到change逐个计算最少硬币数\n",
    "    for cents in range(1, change+1):\n",
    "        #1、初始化一个最大值\n",
    "        coinCount = cents\n",
    "        #2、减去每一个硬币，向后查找最少硬币数，同时记录总的最少数\n",
    "        for j in [c for c in coinValueList if c <= cents]:\n",
    "            if minCoins[cents - j] +1 < coinCount:\n",
    "                coinCount = minCoins[cents - j] + 1\n",
    "        #3、得到最少当前硬币数，记录到表中\n",
    "        minCoins[cents] = coinCount\n",
    "    return minCoins[change]\n",
    "\n",
    "print(dpMakeChange([1,5,10,21,25], 5, [0]*64))        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Making change for 63 requires\n",
      "3 Coins\n",
      "They are:\n",
      "21\n",
      "21\n",
      "21\n",
      "The used list is as follows:\n",
      "[1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 21, 1, 1, 1, 25, 1, 1, 1, 1, 5, 10, 1, 1, 1, 10, 1, 1, 1, 1, 5, 10, 21, 1, 1, 10, 21, 1, 1, 1, 25, 1, 10, 1, 1, 5, 10, 1, 1, 1, 10, 1, 10, 21]\n"
     ]
    }
   ],
   "source": [
    "#动态规划\n",
    "def dpMakeChange(coinValueList,change,minCoins,coinsUsed):\n",
    "    #从1分钱开始到change逐个计算最少硬币数\n",
    "    for cents in range(change+1):\n",
    "        coinCount = cents\n",
    "        newCoin = 1   #初始化新加硬币\n",
    "        #2、减去每一个硬币，向后查找最少硬币数，同时记录总的最少数\n",
    "        for j in [c for c in coinValueList if c <= cents]:\n",
    "            if minCoins[cents - j] +1 < coinCount:\n",
    "                coinCount = minCoins[cents - j] + 1\n",
    "                newCoin = j\n",
    "        #3、得到最少当前硬币数，记录到表中\n",
    "        minCoins[cents] = coinCount\n",
    "        coinsUsed[cents] = newCoin    #记录本步骤加的一个硬币\n",
    "    return minCoins[change]\n",
    "\n",
    "def printCoins(coinsUsed, change):\n",
    "    coin = change\n",
    "    while coin > 0:\n",
    "        thisCoin = coinsUsed[coin]\n",
    "        print(thisCoin)\n",
    "        coin = coin - thisCoin\n",
    "        \n",
    "amnt = 63\n",
    "clist = [1,5,10,21,25]\n",
    "coinsUsed = [0] * (amnt + 1)\n",
    "coinCount = [0] * (amnt + 1)\n",
    "print('Making change for', amnt, 'requires')\n",
    "print(dpMakeChange(clist,amnt,coinCount,coinsUsed),'Coins')\n",
    "print('They are:')\n",
    "printCoins(coinsUsed,amnt)\n",
    "print('The used list is as follows:')\n",
    "print(coinsUsed)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "29\n"
     ]
    }
   ],
   "source": [
    "#博物馆大盗\n",
    "tr = [None, {'w':2,'v':3},{'w':3,'v':4},{'w':4,'v':8},{'w':5,'v':8},{'w':9,'v':10}]\n",
    "\n",
    "max_w = 20\n",
    "#初始化二维表格m[(i,w)]\n",
    "m = {(i,w):0 for i in range(len(tr))\n",
    "                for w in range(max_w+1)}\n",
    "\n",
    "for i in range(1,len(tr)):\n",
    "    for w in range(1,max_w+1):\n",
    "        if tr[i]['w'] > w:             #装不下第i件宝物\n",
    "            m[(i,w)] = m[(i-1,w)]\n",
    "        else:                       #不装第i个宝物和装第i个宝物，两种情况下最大值\n",
    "            m[(i,w)] = max(\n",
    "                        m[(i-1,w)],\n",
    "                        m[(i-1,w-tr[i]['w'])] + tr[i]['v'])\n",
    "\n",
    "print(m[len(tr)-1,max_w])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "faker",
   "language": "python",
   "name": "faker"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
